package com.company.剑指offer每日刷题.专项版;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 题目：剑指 Offer II 006. 排序数组中两个数字之和
 * 给定一个已按照 升序排列的整数数组numbers ，请你从数组中找出两个数满足相加之和等于目标数target 。
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0开始计数 ，所以答案数组应当满足 0<= answer[0] < answer[1] <numbers.length。
 * 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
 * <p>
 * 示例 1：
 * 输入：numbers = [1,2,4,6,10], target = 8
 * 输出：[1,3]
 * 解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
 *
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kLl5u1
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TwoSum {
    public static void main(String[] args) {
        TwoSum obj = new TwoSum();
        int[] res = obj.twoSum2(new int[]{1,2,4,6,7,10}, 9);
//        int[] res = obj.twoSum1(new int[]{0,0,0,0,0,0,0,1},0);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 方法1 ：暴力列举法
     * 时间复杂度 O(n^2)
     * 存在问题（超时）
     */
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        List<Integer> integerList = Arrays.stream(numbers).boxed().collect(Collectors.toList());
        int i = 0;
        while (i < numbers.length - 1 && target >= 2 * numbers[i]) {
            int lastindex = integerList.lastIndexOf(target - numbers[i]);
            if (i < lastindex) {
                res[0] = i;
                res[1] = lastindex;
                break;
            }
            i++;
        }
        return res;
    }

    /**
     * 方法2 ：二分查找
     * 思路： 因为给定的数组是有序的，可以先固定一个数，然后通过二分查找去找另一个数字
     * 时间复杂度 ： nlogn
     */
    public int[] twoSum1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            int index = binarySearch(numbers, i + 1, numbers.length - 1, target - numbers[i]);
            if (index > 0) {
                return new int[]{i, index};
            }
        }
        return new int[]{0, 0};
    }

    private int binarySearch(int[] number, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (number[mid] == target) {
                return mid;
            } else if (number[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    /**
     * 方法3： 双指针法
     * 思路： 用两个指针，分别指向数组的两端，也就是最左边的是最小的数，最右边的是最大的数，
     *      当两个指针所指向的数之和 > 目标值 时，我们就将右边指针向左移1单元来减小他们的和
     *      当两个指针所指向的数之和 < 目标值 时，我们就将左边指针向右移1单元来增大他们的和
     *      循环上面的操作，直到找到等于 目标值的解，返回之
     * 时间复杂度： O(n)
     * */
    public int[] twoSum2(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        while(left < right){
            if(numbers[left] + numbers[right] > target){
                right--;
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }else{
                return new int[]{left ,right};
            }
        }
        return new int[]{0,0};
    }


}
